from typing import List

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        ans_max = nums[0]
        pre = 0
        for i in range(len(nums)):
            pre = max(pre+nums[i],nums[i])
            ans_max = max(ans_max,pre)
        return ans_max


'''
复杂度

时间复杂度：O(n)，其中 n 为 nums 数组的长度。我们只需要遍历一遍数组即可求得答案。
空间复杂度：O(1)。我们只需要常数空间存放若干变量。

'''
nums = [-2,1,-3,4,-1,2,1,-5,4]
# nums = [1]
# nums = [5,4,-1,7,8]
# nums = [-2,1]
# nums = [1,-1,1]



print(Solution().maxSubArray(nums))

